package leetcode.code;

import java.util.Arrays;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution16 implements IDebug {

	public int threeSumClosest(int[] nums, int target) {
		Arrays.sort(nums);
		int ans = 0;
		int abs = Integer.MAX_VALUE;
		int len = nums.length;
		for (int i = 0; i < len - 2; i++) {
			int t = nums[i];
			int l = i + 1;
			int r = len - 1;
			while (l < r) {
				int aim = t + nums[l] + nums[r];
				if (aim == target) {
					return aim;
				} else if (aim > target) {
					r--;
				} else {
					l++;
				}
				int diff = Math.abs(target - aim);
				if (diff < abs) {
					abs = diff;
					ans = aim;
				}
			}
		}
		return ans;
	}

	public int threeSumClosest1(int[] nums, int target) {
		Arrays.sort(nums);
		int ans = 0;
		int abs = Integer.MAX_VALUE;
		int len = nums.length;
		for (int i = 0; i < len - 2; i++) {
			int t = nums[i];
			int l = i + 1;
			int r = len - 1;
//			int d = Integer.MAX_VALUE;
			while (l < r) {
				int aim = t + nums[l] + nums[r];
				if (aim == target) {
					return aim;
				} else if (aim > target) {
					r--;
				} else {
					l++;
				}
				int diff = Math.abs(target - aim);
//				if (diff <= d) {
//					d = diff;
				if (diff < abs) {
					abs = diff;
					ans = aim;
				}
//				} else {
//					break;
//				}
			}
		}
		return ans;
	}

	@Override
	public void debug1() {
		String str = "[-1,2,1,-4]";
		int[] nums = HelpDebug.str2array3(str);
		int target = 1;
		int e = 2;
		int r = this.threeSumClosest(nums, target);
		HelpDebug.compare(e, r);
	}

	@Override
	public void debug2() {
		String str = "[1,2,2,4,4]";
		int[] nums = HelpDebug.str2array3(str);
		int target = 9;
		int e = 9;
		int r = this.threeSumClosest(nums, target);
		HelpDebug.compare(e, r);
	}

	@Override
	public void debug3() {
		String str = "[-55,-24,-18,-11,-7,-3,4,5,6,9,11,23,33]";
		int[] nums = HelpDebug.str2array3(str);
		int target = 0;
		int e = 0;
		int r = this.threeSumClosest(nums, target);
		HelpDebug.compare(e, r);
	}

	@Override
	public void debug4() {
		String str = "[-1,2,1,-4]";
		int[] nums = HelpDebug.str2array3(str);
		int target = 1;
		int e = 2;
		int r = this.threeSumClosest(nums, target);
		HelpDebug.compare(e, r);
	}

	public static void main(String[] args) {
		Solution16 so = new Solution16();
		so.debug4();
		so.debug1();
		so.debug2();
		so.debug3();

	}

}
